The present invention relates generally to computer networking. More specifically, the present invention relates to methods and apparatuses for distributing frame transmissions as evenly as possible across a group of ports which are logically grouped into a single port.
A common computer network implementation includes a plurality of clients, such as personal computers or work stations, connected to each other and one or more servers via a switch or router by network cable. In the present application, the term xe2x80x9cswitchxe2x80x9d is intended to mean any network device that forwards packets from a source to a destination, rather than broadcasting them (i.e., includes router, but excludes repeater). The network is configured to operate at one or more data transmission rates, typically 10 Mbit/sec (e.g., 10 Base-T Ethernet), or 100 Mbit/sec (e.g., 100 Base-T Fast Ethernet). More recently, Gigabit data transmission rates have become attainable. Data is forwarded on the network in packets which are typically received by a switch from a source network device and then directed to the appropriate destination device. The receipt and transmission of data packets by a switch occurs via ports on the switch. Packets travelling from the same source to the same destination are defined as members of the same stream.
Since network switches typically receive data from and transmit data to several network devices, and the cable connections between the various network devices typically transmit data at the same rate, a bottle-neck may be created when, for example, several devices (e.g., clients) are simultaneously attempting to send data to a single other device (e.g., a server). In this situation, the data packets must sit in a queue at the port for the server and wait for their turn to be forwarded from the switch to the server.
One way to relieve this bottle-neck is to provide a logical grouping of multiple ports into a single port. The bandwidth of the new port is increased since it has multiple lines (cables) connecting a switch and another network device, each line capable of carrying data at the same rate as the line connecting data sources to the switch. This grouping of ports is sometimes referred to as a port aggregation or port group. One example of such a port aggregation implementation is Cisco Technology, Inc.""s Fast EtherChannel(trademark) port group in a Fast Ethernet network. Further information regarding Fast EtherChannel(trademark) may be found on Cisco Technology, Inc.""s World Wide Web site www.cisco.com. This information is incorporated by reference herein for all purposes.
In order for networking equipment to make optimal utilization of the increased bandwidth provided by a port group, packet transmissions must be distributed as evenly as possible across the ports of the group. In addition, a suitable distribution system will ensure that packets in the same stream are not forwarded out of order.
Traffic distribution for ports grouped in port groups has conventionally been accomplished by static distribution of addresses across the ports of a group. In one example of such a static distribution of network traffic, as a packet of data to be forwarded is received by a switch, its destination address is determined, and it is assigned to the port group connecting with its destination. Assignment to a port within the port group may be done in a number of ways. For example, each packet assigned to the port group may be assigned to the next port in a cycle through the ports, or the assignment may be based on the packet""s source address. However it is done, this assignment is permanent, so that if a second packet with the same address is subsequently received by the switch, it is assigned to the same port assigned to the previous packet with that address. The one exception to this permanent assignment in conventional systems may be the removal of an address due to aging, that is, if a long enough period of time (e.g., 10 to 1,000,000 seconds, typically 300 seconds) passes between the receipt of two packets of data having the same address, the second packet may be assigned to a different port. Another static address distribution system performs a simple logical operation on a packet""s source and destination addresses (exclusive OR of the two least significant bits of the addresses) in order to identify the port within a group to be used to transmit a packet.
Static address distribution systems ensure that packets from a given stream are not forwarded out of order by permanently assigning the stream to a particular port. In this way, packets in a stream can never be forwarded to their destination by the switch out of order. For example, an earlier packet in the stream may not be forwarded by the switch before a later one via a different less-busy port in the group since all packets from that stream will always be forwarded on the same port in the group.
While static address distribution improves the efficiency of data transmission over a port group by distributing packet streams among the various ports of a port group, it does not account for the amount of traffic volume of different streams. Accordingly, static address distribution evenly (and thus most efficiently) distributes traffic over the ports of a port group of a switch only if there is the same amount of data being forwarded in each stream. If a given stream is transmitting much more than the average amount of data for streams being forwarded through the port group, then there may be inefficiencies in the data transmission in a static address distribution system. For example, this situation may result in there being a long queue for the port to which the heavily loaded stream is assigned, while other ports in the group, which are assigned to more lightly loaded streams, are available to transmit data.
Accordingly, what is needed is an improved distribution system for network port groups that satisfies the port groups"" distribution and packet ordering requirements, while taking into consideration the amount of data being forwarded in a given stream.
The present invention meets this need by providing methods, apparatuses and systems for balancing the load of data transmissions through a port aggregation. The methods, apparatuses and systems of the present invention allocate port assignments based on load, that is, the amount of data being forwarded through each port in the group. The load balancing of the present invention is preferably dynamic, that is, packets from a given stream may be forwarded on different ports depending upon each port""s current utilization. When a new port is selected to transmit a particular packet stream, it is done so that the packets cannot be forwarded out of order. This is preferably accomplished by ensuring passage of a period of time sufficient to allow all packets of a given stream to be forwarded by a port before a different port is allocated to transmit packets of the same stream. The invention may be used in a variety of different network environments and speeds, including 10 Base-T, 100 Base-T, and Gigabit Ethernet, and other network environments.
In one aspect, the present invention provides a method of distributing traffic over a network port group. The method involves receiving a packet of data to be forwarded, determining a stream ID for the packet, and determining whether a prior packet having that stream ID has been distributed to a queue on a port in the group during a predetermined time interval. Where a prior packet having that stream ID has not been distributed to a queue on a port of the group during the predetermined time interval, the method involves allocating the packet to a queue of a port having a lesser load in its queue than a queue of any other port of the group. The method may also involve, where a prior packet having that stream ID has been distributed to a queue on a port of the group during the predetermined time interval, allocating the packet to that queue. In addition, the method may involve monitoring the port group queues to maintain proper identification of the least utilized queue.
In another aspect, the invention provides a network switch. The switch includes a port group and a system for distributing network traffic among ports of the port group. The system includes a mechanism for determining a stream ID for the packet and assigning the packet having the stream ID to a queue of a port in the port group, and a mechanism for adjusting a queue assignment of a prior packet having the stream ID to a queue of a different port of the port group based on load in the queues of the ports of the group. The mechanism for determining a stream ID and assigning the packet having the stream ID to a queue of a port in the port group may include a hashing and masking mechanism for determining a stream ID for the packet, a pair of time mark registers for determining whether another packet having the stream ID has been distributed to a queue for a port in the group during a time interval, and a stream state table for storing stream IDs with corresponding queue assignments. The adjusting mechanism may include a least utilized queue register for maintaining proper identification of a least utilized queue, and a pair of queue mark registers for determining whether a queue for a port in the port group is current. In addition, the switch may include a clock for timing a load balance time interval.
In a further aspect, the invention provides a computer program product including a computer-usable medium having computer-readable program code embodied thereon relating to updating current and alternate time mark registers for a dynamic load balancing of traffic on a port aggregation, the computer program product having computer-readable program code for effecting the following steps within a computing system: Determining whether a load balance time interval has passed; where the load balance time interval has passed, determining for each queue of the port group, whether a queue mark indicate bit assigned to packets exiting the queue is equal to a queue mark bit being assigned to packets entering the queue; where the queue mark indicate bit is the same as the queue mark bit, clearing all alternate time mark register bits, and toggling (i.e., changing from 0/1 or vice versa) all queue mark bits; and, switching the current and alternate time mark registers.